package a202110.day08;

import java.util.Arrays;

/**
 * 最小操作次数使数组元素相等
 * <p>
 * 给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。
 * 返回让数组所有元素相等的最小操作次数。
 * <p>
 * 输入：nums = [1,2,3]
 * 输出：3
 * 解释：
 * 只需要3次操作（注意每次操作会增加两个元素的值）：
 * [1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]
 * <p>
 * 输入：nums = [1,1,1]
 * 输出：0
 * <p>
 * 提示:
 * n == nums.length
 * 1 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 * 答案保证符合 32-bit 整数
 *
 * @author yousj
 * @since 2021/10/20
 */
public class Main {

    public static void main(String[] args) {
        // 思路
        // 假设总操作次数为 m, 最终相等的数为 x, 当前数组和为 sum, 当前数组最小值为 min
        // 那么有 x * n = sum + m * (n - 1)
        // 而 m = x - min, 即 x = m + min
        // 从而得出 (m + min) * n = sum + m * (n - 1)
        // => m * n + min * n = sum + m * n - m
        // => m = sum - min * n
        int[] nums = new int[]{1, 2, 3};
        System.out.println(minMoves1(nums));
    }


    private static int minMoves(int[] nums) {
        return Arrays.stream(nums).sum() - Arrays.stream(nums).min().getAsInt() * nums.length;
    }

    private static int minMoves1(int[] nums) {
        int length = nums.length;
        int sum = 0;
        int min = nums[0];
        for (int num : nums) {
            sum += num;
            if (min > num) min = num;
        }
        return sum - min * length;
    }
}
